package com.sicheng.algorithm.dynamic;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/10/25 19:14
 */
public class 最长回文子串 {
    public static void main(String[] args) {

        System.out.println(longestPalindrome("caabaad"));
    }

    /**
     * dp解法
     * 时间:O(n^2)
     * 空间:O(n^2)
     */
    public static String longestPalindrome(String s) {
        int maxlenth = 0;
        int left = 0;
        int right = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];
//        Arrays.fill(dp, false);

        System.out.println(Arrays.deepToString(dp));
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1) { // 情况一 和 情况二
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) { // 情况三
                        dp[i][j] = true;
                    }
                }
                if (dp[i][j] && j - i + 1 > maxlenth) {
                    maxlenth = j - i + 1;
                    left = i;
                    right = j;
                }
            }

        }
        return s.substring(left, right + 1);
    }


    //中心扩散  双指针


}
